package sort;

import java.util.Arrays;

/**
 * MergeSort
 *
 * @author admin
 * @version 2023/11/02 14:18
 **/
public class MergeSort implements SortStrategy{
    @Override
    public void sort(int[] a) {
        a=cutHalf(a);
        System.out.println(Arrays.toString(a));
    }
    public int[] cutHalf(int[] a)
    {
        if(a.length<2){
            return a;
        }
        int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
        int[] right=Arrays.copyOfRange(a,a.length/2,a.length);

        return merge(cutHalf(left),cutHalf(right));
    }
    public int[] merge(int[] left,int[] right){
        int i=0;
        int j=0;
        int[] res=new int[left.length+right.length];
        while(i<left.length||j<right.length)
        {
            if(i>=left.length){
                res[i+j]=right[j];
                j++;
            }
            else if(j>=right.length)
            {
                res[i+j]=left[i];
                i++;
            }
            else{
                if(left[i]<right[j]){
                    res[i+j]=left[i];
                    i++;
                }
                else{
                    res[i+j]=right[j];
                    j++;
                }
            }
        }
        return res;
    }
}
